수행시간 분석

n개의 입력이 있을때 f(n)의 결과가 커지는지 보는것.
즉 함수 그래프를 생각했을때 기울기가 높은지 낮은지 본다는것이다.
y=x^2랑 y=100x가 있으면 x가 작을때는 앞의 함수가 작은 y값을 가지지만, x의 값이 어느 선을 지나면 뒤의 함수가 더 작은 y값을 가진다.

증가율

f(n) = n^4 + 500n + n^2 이라면
보통 가장 차수가 큰 n^4만 고려해서 f(n)은 대략 n^4의 수행시간이 걸린다고 한다.
프로그래밍과 컴퓨터의 특성상 큰 수를 다루는 경우가 지배적인데 큰 수를 다룰땐 특히 작은 차수를 가진 숫자의 중요도가 더 낮아진다.

많이 사용되는 증가율

• 1
• log n
• n
• n log n
• n^2
• n^3
• 2^n

분석의 종류

최선의 경우
최악의 경우
평균의 경우

점근적 표기법

빅-O 표기법 Big-O Notation

함수에 대한 가장 근접한 상한선(g(n))을 찾는다.
위의 증가율에서 말했던것 처럼 f(n) = n^4 + 500n + n^2 라면,
f(n)는 대략 n^4보다 확실히 구분될만큼 높은 증가율 을 가지지 않는다는 의미에서
가장 근접한 상한선을 n^4라고 하고 O(n^4) 라고 표기한다.

오메가 표기법

오메가 표기법은 하한선을 찾는다.
이것도 마찬가지로 f(n) = n^4 + 500n + n^2 를 가지고 보면,
f(n)은 적어도 n^4 보다는 높을 증가율을 가진다.
그래서 오메가 표기법으로도 오메가(n^4) 라고 할 수 있다.

세타 표기법

세타 표기법은 빅오와 오메가가 같을 때는 세타다.
즉 대부분의 사람들이 관습적으로 '빅오 표기법'이라고 할 때의 의미는 세타인 경우가 대다수.